class Solution {
public:
    int medianOfUniquenessArray(vector<int>& nums)
    {
        //本题的解题方法就是：制作出唯一性数组
            //由于数据范围原因，直接暴力制作出唯一性数组就会TLE，所以本题难点就是找到不TLE也能制作出该数组的办法。
        //找到唯一性数组的中位数
        int n = nums.size();

        //唯一性数组的长度的中位数
        long long m = ((long long)n * (n + 1) / 2 + 1) / 2;
        auto check = [&](int lim)
            {
                int left = 0;
                long long cnt = 0;
                unordered_map<int, int> hash;
                for (int right = 0; right < n; right++)
                {
                    hash[nums[right]]++;
                    while (hash.size() > lim)
                    {
                        if (--hash[nums[left]] == 0) hash.erase(nums[left]);
                        left++;
                    }
                    cnt += right - left + 1;
                    if (cnt >= m) return true;
                }
                return false;
            };

        int l = 0, r = n;
        while (l + 1 < r)
        {
            int mid = l + ((r - l) >> 1);
            (check(mid) ? r : l) = mid;
        }
        return r;

    }
};